# -*- coding: utf-8 -*-
# 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符
# 返回被除数 dividend 除以除数 divisor 得到的商
# 示例 1:
# 输入: dividend = 10, divisor = 3
# 输出: 3

# 示例 2:
# 输入: dividend = 7, divisor = -3
# 输出: -2

# 说明:
# 被除数和除数均为 32 位有符号整数
# 除数不为 0
# 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−pow(2, 31),  pow(2, 31) − 1]。本题中，如果除法结果溢出，则返回 pow(2, 31) − 1

# 哈哈这样肯定要超时呀！！
# class Solution(object):
#     def divide(self, dividend, divisor):
#         """
#         :type dividend: int
#         :type divisor: int
#         :rtype: int
#         """
#         if divisor == 1:
#             return dividend;
#         if divisor == -1:
#             if dividend == -pow(2, 31):
#                 return pow(2, 31) - 1;
#             return -dividend;

#         dividend_signal = 1 if dividend >= 0 else -1;
#         divisor_signal = 1 if divisor >= 0 else -1;
#         signal = 1 if dividend_signal == divisor_signal else -1;
#         if dividend_signal == 1:
#             dividend = -dividend;
#         if divisor_signal == 1:
#             divisor = -divisor;

#         rtn = 0;
#         print [dividend, divisor];
#         while dividend <= 0:
#             dividend -= divisor;
#             print dividend;
#             rtn += 1;

#         if signal == - 1:
#             return 1 - rtn;
#         else:
#             return rtn - 1;

# class Solution(object):
#     def divide(self, dividend, divisor):
#         """
#         :type dividend: int
#         :type divisor: int
#         :rtype: int
#         """
#         if divisor == 1:
#             return dividend;
#         if divisor == -1:
#             if dividend == -2**31:
#                 return 2**31 - 1;
#             return -dividend;

#         dividend_signal = 1 if dividend >= 0 else -1;
#         divisor_signal = 1 if divisor >= 0 else -1;
#         signal = 1 if dividend_signal == divisor_signal else -1;
#         if dividend_signal == 1:
#             dividend = -dividend;
#         if divisor_signal == 1:
#             divisor = -divisor;

#         increase_divisor = [divisor];
#         increase_rtn = [1];
#         rtn = 0;
#         while len(increase_divisor) > 0:
#             dividend -= increase_divisor[-1];
#             if dividend > 0:
#                 dividend += increase_divisor[-1];
#                 increase_divisor.pop();
#                 increase_rtn.pop();
#             else:
#                 increase_divisor.append(increase_divisor[-1] + increase_divisor[-1]);
#                 rtn += increase_rtn[-1];
#                 increase_rtn.append(increase_rtn[-1] + increase_rtn[-1]);

#         if signal == 1:
#             return rtn;
#         else:
#             return -rtn;








# 查看最快的解决方案，未使用数组
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor == 1:
            return dividend;
        if divisor == -1:
            if dividend == -2**31:
                return 2**31 - 1;
            return -dividend;

        dividend_signal = 1 if dividend >= 0 else -1;
        divisor_signal = 1 if divisor >= 0 else -1;
        signal = 1 if dividend_signal == divisor_signal else -1;
        if dividend_signal == 1:
            dividend = -dividend;
        if divisor_signal == 1:
            divisor = -divisor;

        increase_multi = 0;
        rtn = 0;
        while increase_multi >= 0:
            dividend -= divisor << increase_multi;
            if dividend > 0:
                dividend += divisor << increase_multi;
                increase_multi -= 1;
            else:
                rtn += 1 << increase_multi;
                increase_multi += 1;

        if signal == 1:
            return rtn;
        else:
            return -rtn;
            
t = Solution();
print t.divide(-10, 8);